package third

import "math"

/*
	输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

	要求时间复杂度为O(n)。

	示例1:

	输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
	输出: 6
	解释:连续子数组[4,-1,2,1] 的和最大，为6。

	提示：

	1 <=arr.length <= 10^5
	-100 <= arr[i] <= 100

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

func maxSubArray(nums []int) int {
	// 因为是要【连续】子数组的和、所以要考虑到每次在比较大小的时候、只能取nums[i]的值或者前面的连续子数组的和+nums[i]的值中较大的那个值
	dp := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		dp[i] = nums[i]
	}
	for i := 1; i < len(nums); i++ {
		if dp[i-1]+nums[i] > nums[i] {
			dp[i] = dp[i-1]+nums[i]
		} else {
			dp[i] = nums[i]
		}
	}
	maxSum:=math.MinInt32
	for i := 0;i < len(dp);i++ {
		maxSum = max(maxSum, dp[i])
	}
	return maxSum
}
